home *** CD-ROM | disk | FTP | other *** search
/ InterCD 2000 September / september_2000.iso / intercd / root / ^Linux / WindowMaker / WINGs / hashtable.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-09  |  7.3 KB  |  407 lines
  1.  
  2.  
  3. #include <sys/types.h>
  4. #include <string.h>
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7.  
  8. #include "WUtil.h"
  9.  
  10.  
  11.  
  12.  
  13. #define INITIAL_CAPACITY    23
  14.  
  15.  
  16. #if defined(__GNUC__) && !defined(__STRICT_ANSI__)
  17. # define INLINE inline
  18. #else
  19. # define INLINE
  20. #endif
  21.  
  22.  
  23. typedef struct HashItem {
  24.     void *key;
  25.     void *data;
  26.     
  27.     struct HashItem *next;           /* collided item list */
  28. } HashItem;
  29.  
  30.  
  31. typedef struct W_HashTable {
  32.     WMHashTableCallbacks callbacks;
  33.  
  34.     unsigned itemCount;
  35.     unsigned size;               /* table size */
  36.  
  37.     HashItem **table;
  38. } HashTable;
  39.  
  40.  
  41.  
  42.  
  43. #define HASH(table, key)  (((table)->callbacks.hash ? \
  44.         (*(table)->callbacks.hash)(key) : hashPtr(key)) % (table)->size)
  45.  
  46. #define DUPKEY(table, key) ((table)->callbacks.retainKey ? \
  47.             (*(table)->callbacks.retainKey)(key) : (key))
  48.  
  49. #define RELKEY(table, key) if ((table)->callbacks.releaseKey) \
  50.             (*(table)->callbacks.releaseKey)(key)
  51.  
  52.  
  53.  
  54.  
  55. static INLINE unsigned
  56. hashString(const char *key)
  57. {
  58.     unsigned ret = 0;
  59.     unsigned ctr = 0;
  60.  
  61.     while (*key) {
  62.     ret ^= *(char*)key++ << ctr;
  63.     ctr = (ctr + 1) % sizeof (char *);
  64.     }
  65.     
  66.     return ret;
  67. }
  68.  
  69.  
  70.  
  71. static INLINE unsigned
  72. hashPtr(const void *key)
  73. {
  74.     return ((size_t)key / sizeof(char*));
  75. }
  76.  
  77.  
  78.  
  79.  
  80. static void
  81. rellocateItem(WMHashTable *table, HashItem *item)
  82. {
  83.     unsigned h;
  84.  
  85.     h = HASH(table, item->key);
  86.  
  87.     item->next = table->table[h];
  88.     table->table[h] = item;
  89. }
  90.  
  91.  
  92. static void
  93. rebuildTable(WMHashTable *table)
  94. {
  95.     HashItem *next;
  96.     HashItem **oldArray;
  97.     int i;
  98.     int oldSize;
  99.     int newSize;
  100.  
  101.     oldArray = table->table;
  102.     oldSize = table->size;
  103.  
  104.     newSize = table->size*2;
  105.  
  106.     table->table = wmalloc(sizeof(char*)*newSize);
  107.     memset(table->table, 0, sizeof(char*)*newSize);
  108.     table->size = newSize;
  109.     
  110.     for (i = 0; i < oldSize; i++) {
  111.     while (oldArray[i]!=NULL) {
  112.         next = oldArray[i]->next;
  113.         rellocateItem(table, oldArray[i]);
  114.         oldArray[i] = next;
  115.     }
  116.     }
  117.     wfree(oldArray);
  118. }
  119.  
  120.  
  121.  
  122. WMHashTable*
  123. WMCreateHashTable(WMHashTableCallbacks callbacks)
  124. {
  125.     HashTable *table;
  126.     
  127.     table = wmalloc(sizeof(HashTable));
  128.     memset(table, 0, sizeof(HashTable));
  129.     
  130.     table->callbacks = callbacks;
  131.     
  132.     table->size = INITIAL_CAPACITY;
  133.  
  134.     table->table = wmalloc(sizeof(HashItem*)*table->size);
  135.     memset(table->table, 0, sizeof(HashItem*)*table->size);
  136.     
  137.     return table;
  138. }
  139.  
  140.  
  141. void
  142. WMResetHashTable(WMHashTable *table)
  143. {
  144.     HashItem *item, *tmp;
  145.     int i;
  146.  
  147.     for (i = 0; i < table->size; i++) {
  148.     item = table->table[i];
  149.     while (item) {
  150.         tmp = item->next;
  151.         RELKEY(table, item);
  152.         wfree(item);
  153.         item = tmp;
  154.     }
  155.     }
  156.  
  157.     table->itemCount = 0;
  158.     
  159.     if (table->size > INITIAL_CAPACITY) {
  160.     wfree(table->table);
  161.     table->size = INITIAL_CAPACITY;
  162.     table->table = wmalloc(sizeof(HashItem*)*table->size);
  163.     }
  164.     memset(table->table, 0, sizeof(HashItem*)*table->size);
  165. }
  166.  
  167.  
  168. void
  169. WMFreeHashTable(WMHashTable *table)
  170. {
  171.     HashItem *item, *tmp;
  172.     int i;
  173.     
  174.     for (i = 0; i < table->size; i++) {
  175.     item = table->table[i];
  176.     while (item) {
  177.         tmp = item->next;
  178.         RELKEY(table, item->key);
  179.         wfree(item);
  180.         item = tmp;
  181.     }
  182.     }
  183.     wfree(table->table);
  184.     wfree(table);
  185. }
  186.  
  187.  
  188.  
  189. void*
  190. WMHashGet(WMHashTable *table, const void *key)
  191. {
  192.     unsigned h;
  193.     HashItem *item;
  194.     
  195.     h = HASH(table, key);
  196.     item = table->table[h];
  197.     
  198.     if (table->callbacks.keyIsEqual) {
  199.     while (item) {
  200.         if ((*table->callbacks.keyIsEqual)(key, item->key)) {
  201.         break;
  202.         }
  203.         item = item->next;
  204.     }
  205.     } else {
  206.     while (item) {
  207.         if (key == item->key) {
  208.         break;
  209.         }
  210.         item = item->next;
  211.     }
  212.     }
  213.     if (item)
  214.     return item->data;
  215.     else
  216.     return NULL;
  217. }
  218.  
  219.  
  220.  
  221. void*
  222. WMHashInsert(WMHashTable *table, void *key, void *data)
  223. {
  224.     unsigned h;
  225.     HashItem *item;
  226.     int replacing = 0;
  227.     
  228.     h = HASH(table, key);
  229.     /* look for the entry */
  230.     item = table->table[h];
  231.     if (table->callbacks.keyIsEqual) {
  232.     while (item) {
  233.         if ((*table->callbacks.keyIsEqual)(key, item->key)) {
  234.         replacing = 1;
  235.         break;
  236.         }
  237.         item = item->next;
  238.     }
  239.     } else {
  240.     while (item) {
  241.         if (key == item->key) {
  242.         replacing = 1;
  243.         break;
  244.         }
  245.         item = item->next;
  246.     }
  247.     }
  248.     
  249.     if (replacing) {
  250.     void *old;
  251.  
  252.     old = item->data;
  253.     item->data = data;
  254.     RELKEY(table, item->key);
  255.     item->key = DUPKEY(table, key);
  256.  
  257.     return old;
  258.     } else {
  259.     HashItem *nitem;
  260.  
  261.     nitem = wmalloc(sizeof(HashItem));
  262.     nitem->key = DUPKEY(table, key);
  263.     nitem->data = data;
  264.     nitem->next = table->table[h];
  265.     table->table[h] = nitem;
  266.  
  267.     table->itemCount++;
  268.     }
  269.     
  270.     /* OPTIMIZE: put this in an idle handler.*/
  271.     if (table->itemCount > table->size) {
  272. #ifdef DEBUG0
  273.     printf("rebuilding hash table...\n");
  274. #endif
  275.     rebuildTable(table);
  276. #ifdef DEBUG0
  277.     printf("finished rebuild.\n");
  278. #endif
  279.     }
  280.     
  281.     return NULL;
  282. }
  283.  
  284.  
  285. static HashItem*
  286. deleteFromList(HashTable *table, HashItem *item, const void *key)
  287. {
  288.     HashItem *next;
  289.     
  290.     if (item==NULL)
  291.     return NULL;
  292.  
  293.     if ((table->callbacks.keyIsEqual 
  294.      && (*table->callbacks.keyIsEqual)(key, item->key))
  295.     || (!table->callbacks.keyIsEqual && key==item->key)) {
  296.     
  297.     next = item->next;
  298.     RELKEY(table, item->key);
  299.     wfree(item);
  300.     
  301.     table->itemCount--;
  302.  
  303.     return next;
  304.     }
  305.     
  306.     item->next = deleteFromList(table, item->next, key);
  307.  
  308.     return item;
  309. }
  310.  
  311.  
  312. void
  313. WMHashRemove(WMHashTable *table, const void *key)
  314. {
  315.     unsigned h;
  316.     
  317.     h = HASH(table, key);
  318.     
  319.     table->table[h] = deleteFromList(table, table->table[h], key);
  320. }
  321.  
  322.  
  323. WMHashEnumerator
  324. WMEnumerateHashTable(WMHashTable *table)
  325. {
  326.     WMHashEnumerator enumerator;
  327.     
  328.     enumerator.table = table;
  329.     enumerator.index = 0;
  330.     enumerator.nextItem = table->table[0];
  331.     
  332.     return enumerator;
  333. }
  334.  
  335.  
  336.  
  337. void*
  338. WMNextHashEnumeratorItem(WMHashEnumerator *enumerator)
  339. {
  340.     void *data = NULL;
  341.  
  342.     /* this assumes the table doesn't change between 
  343.      * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
  344.  
  345.     if (enumerator->nextItem==NULL) {
  346.     HashTable *table = enumerator->table;
  347.     while (++enumerator->index < table->size) {
  348.         if (table->table[enumerator->index]!=NULL) {
  349.         enumerator->nextItem = table->table[enumerator->index];
  350.         break;
  351.         }
  352.     }
  353.     }
  354.     
  355.     if (enumerator->nextItem) {
  356.     data = ((HashItem*)enumerator->nextItem)->data;
  357.     enumerator->nextItem = ((HashItem*)enumerator->nextItem)->next;
  358.     }
  359.     
  360.     return data;
  361. }
  362.  
  363.  
  364. unsigned
  365. WMCountHashTable(WMHashTable *table)
  366. {
  367.     return table->itemCount;
  368. }
  369.  
  370.  
  371. static Bool
  372. compareStrings(const char *key1, const char *key2)
  373. {
  374.     return strcmp(key1, key2)==0;
  375. }
  376.  
  377.  
  378. typedef unsigned (*hashFunc)(const void*);
  379. typedef Bool (*isEqualFunc)(const void*, const void*);
  380. typedef void* (*retainFunc)(const void*);
  381. typedef void (*releaseFunc)(const void*);
  382.  
  383.  
  384. const WMHashTableCallbacks WMIntHashCallbacks = {
  385.     NULL,
  386.     NULL,
  387.     NULL,
  388.     NULL
  389. };
  390.  
  391. const WMHashTableCallbacks WMStringHashCallbacks = {
  392.     (hashFunc)hashString,
  393.     (isEqualFunc)compareStrings,
  394.     (retainFunc)wstrdup,
  395.     (releaseFunc)free
  396. };
  397.  
  398.  
  399.  
  400. const WMHashTableCallbacks WMStringPointerHashCallbacks = {
  401.     (hashFunc)hashString,
  402.     (isEqualFunc)compareStrings,
  403.     NULL,
  404.     NULL
  405. };
  406.  
  407.